#include <stdio.h>
void InsertSort(int* a, int n){
  for(int i = 0; i< n-1; i++){
    int end = i;
    int x = a[end+1];
    while(end >= 0){
      if(a[end] > x){
        a[end+1] = a[end];
        end--;
      }
      else{
        break;
      }
    }
    a[end+1] = x;
  }
}
void ShellSort(int* a,int n){
  int gap = 5;
  while(gap > 1){
    gap /= 2;
    //预排
    for(int i = 0; i < n - gap; i++){
      int end = i;
      int x = a[end+gap];
      while(end >= 0){
        if(a[end] > x){
          a[end + gap] = a[end];
          end -= gap;
        }
        else{
          break;
        }
      }
      a[end+gap] = x;
    }
  }
}
void BubbleSort(int* a,int n){
  int SortBord = n - 1;
  int LastChangeIndex = 0;
  for(int i = 0; i < n-1; i++){
    int flag = 0;
    for(int j = 0; j < SortBord; j++){
      if(a[j]> a[j+1]){
        flag = 1;
        LastChangeIndex = j;
        int tmp = a[j];
        a[j] = a[j+1];
        a[j+1] = tmp;
      }
    }
    SortBord = LastChangeIndex;
    if(flag == 0){
      break;
    }
  }
}
int main(){
  int a[] = {9,1,2,8,3,7,4,6,5};
  int n = sizeof(a)/sizeof(a[0]);
  for(int i = 0; i<n; i++){
    printf("%d ",a[i]);
  }
  printf("\n");
  //InsertSort(a,n);
  //ShellSort(a,n);
  BubbleSort(a,n);
  for(int i = 0; i<n; i++){
    printf("%d ",a[i]);
  }
  printf("\n");
  return 0;
}
